package sort;

public class CountingSort {
    public void sort(int[] nums) {
        int maxValue = getMaxValue(nums);
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : nums)
            bucket[value]++;

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                nums[sortedIndex++] = j;
                bucket[j]--;
            }
        }
    }

    private int getMaxValue(int[] nums) {
        int maxValue = nums[0];
        for (int num : nums)
            if (num > maxValue) maxValue = num;
        return maxValue;
    }

    public static void main(String[] args) {
        CountingSort solution = new CountingSort();
        int[] nums = {1, 1, 0, 0, 3, 5, 8, 7, 6, 3, 5, 4, 2, 0, 8};
        solution.sort(nums);
        Common.printArray(nums);
    }
}
